#!/usr/bin/env python
# -*- coding: utf-8 -*-

import os
import sys
sys.path.append(os.path.join(os.path.dirname(__file__), '..'))
import utils.rand_kit as rand_kit

def lcs(s1, s2):
    g = []
    for n in range(len(s2) + 1):
        arr = []
        g.append(arr)
        for m in range(len(s1) + 1):
            arr.append(0)

    for n in range(len(s2)):
        e2 = s2[n]
        arr = g[n + 1]
        for m in range(len(s1)):
            e1 = s1[m]
            if e1 == e2:
                arr[m + 1] = g[n][m] + 1
            else:
                arr[m + 1] = max(g[n + 1][m], g[n][m + 1])
    
    lcs_len = g[len(s2)][len(s1)]
    print("longest common sequence length: %d" % lcs_len)

    lcs = []
    i = len(s1)
    j = len(s2)
    cnt = lcs_len
    while(cnt > 0):
        if(s1[i - 1] == s2[j - 1]):
            lcs.append(s1[i - 1])
            i -= 1
            j -= 1
            cnt -= 1
        else:
            if(g[j - 1][i] > g[j][i - 1]):
                j -= 1
            else:
                i -= 1
    
    lcs.reverse()
    print("longest common sequence: %s" % ', '.join(str(i) for i in lcs))

# s1 = [1, 3, 4, 5, 6, 7, 7, 8]
# s2 = [3, 5, 7, 4, 8, 6, 7, 8, 2]
s1 = rand_kit.rand_arr()
s2 = rand_kit.rand_arr()
print("sequence 1: %s" % ','.join(str(i) for i in s1))
print("sequence 2: %s" % ','.join(str(i) for i in s2))
lcs(s1, s2)